1. Field of the Invention
The present invention relates to apparatus for detecting and preventing deadlock among multiple processors contending for access to a single resource, such as main memory.
2. Description of Related Art
In multiprocessor computer systems which share a single main storage system, each of the processors in the system may at the same time attempt to access the main storage system. Accordingly, a variety of priority-based algorithms has been developed to assure that at least one of the processors in the system is successful at a given time, while all the processors have access to the main storage system over a period of time.
In mainframe computer systems, such as the Amdahl system 5890, the main storage system is partitioned into a plurality of modules, or interleaves. The data is stored in the modules in an interleaved fashion such that a string of eight lines of data having consecutive addresses will be located in eight different modules of the main store. Further, each of the modules is adapted so that it can be accessed independently of the other modules. In this manner, a main storage system can accept requests for access to more than one module at a time, improving system performance.
In the Amdahl machine, in order to access data in one memory module, a CPU sends a request to a system control unit. Upon accepting a request for a given memory module, the system control unit will raise a busy term for the module to be accessed, so no more requests to that module are accepted by the system control unit until the first access is completed. Further, a predicted busy term for the accessed module is sent to each CPU in the system to minimize pipeline flows making requests to the system control unit for the busy module. The predicted busy term is lowered sooner than the actual busy term in the system control unit, in order to allow for the predicted latency between the time the CPU sets up a request in its pipeline and the time the system control unit receives it.
A contention occurs when several CPUs request the same memory module at a time. If a high priority CPU is in the loop making requests to the system control unit, it can prevent other CPUs from accessing that module. This becomes a deadlock, for example, if the information subject of the high priority CPU request is held by another CPU, and the CPU holding the information cannot access a memory module to release the information.
A prior art approach preventing deadlock involves assigning random priority to the different CPUs in the system. In this manner, a given CPU will not retain its high priority status for a period of time long enough to cause a serious degradation in performance due to deadlocks. This random priority alternative has a number of disadvantages. For instance, all of the CPUs in the system which failed to access the memory module at their last attempt, must make requests to the system control unit in the same cycle as the module is released by the actual busy term. Otherwise, a race condition will be set up that causes a de facto priority for CPUs able to make requests more quickly than others. In order to assure that all requests arrive at the system control unit at the same cycle, a number of constraints are placed on the CPU main store access request logic. Further, the predicted busy term must be eliminated and replaced by an accurate busy term. Because the latency between the CPU request and the completion of a previous access to a memory module varies from process to process, an accurate busy term for supply to each of the CPUs in the system would require very complicated logic or cause the system to suffer performance loss. In addition, the randomization circuit is in itself quite complicated.
Deadlock detection and resolution schemes of the prior art in systems without the predicted busy term are typified by U.S. Pat. No. 4,494,193 invented by Brahm et al., entitled DEADLOCK DETECTION AND RESOLUTION SCHEME. The Brahm et al. patent provides a general background discussion of deadlock schemes in communication systems.
It is found that the predicted busy term provides a substantial performance gain in the Amdahl 5890 systems having two CPUs, which are incapable of entering into a deadlock for the memory modules due to pipeline configuration. Accordingly, it is desirable to maintain the predicted busy logic in the mainframe computer systems while preventing deadlocks for access to the system resources that may occur in systems with more than two CPUs.